HTMLify

class Solution:
    def isWordExist(self, mat, word):
        n = len(mat)
        m = len(mat[0])
        
        def backtrack(r, c, index):
            if index == len(word):
                return True
            
            if r < 0 or r >= n or c < 0 or c >= m or mat[r][c] != word[index]:
                return False
            
            temp = mat[r][c]
            mat[r][c] = '#'
            
            found = (backtrack(r + 1, c, index + 1) or
                     backtrack(r - 1, c, index + 1) or
                     backtrack(r, c + 1, index + 1) or
                     backtrack(r, c - 1, index + 1))
            
            mat[r][c] = temp
            return found

        for i in range(n):
            for j in range(m):
                if mat[i][j] == word[0]:
                    if backtrack(i, j, 0):
                        return True
        return False